package leetcode.weekly.week323;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Allocator {

	int[] arr;
	int n;

	Map<Integer, List<int[]>> map;

	public Allocator(int n) {
		arr = new int[n];
		this.n = n;
		map = new HashMap<>();
	}

	public int allocate(int size, int mID) {
		int ans = -1;
		int i = 0;
		while (i < n) {
			int num = arr[i];
			if (num == 0) {
				int cnt = 0;
				int p = i;
				while (cnt < size && p < n && arr[p] == 0) {
					cnt++;
					p++;
				}
				if (cnt == size) {
					map.computeIfAbsent(mID, key -> new ArrayList<>()).add(new int[] { i, p - 1 });
					ans = i;
					for (int j = i; j < p; j++) {
						arr[j] = mID;
					}
					break;
				}
				i = p;
			} else
				i++;
		}
		return ans;
	}

	public int free(int mID) {
		List<int[]> list = map.get(mID);
		if (list == null) {
			return 0;
		}
		int ans = 0;
		for (int[] lr : list) {
			for (int i = lr[0]; i <= lr[1]; i++) {
				arr[i] = 0;
			}
			ans += lr[1] - lr[0] + 1;
		}
		map.remove(mID);
		return ans;
	}

	public static void main(String[] args) {

		Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
		loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
		loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
		loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
		loc.free(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2
						// 的内存单元。
		loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
		loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
		loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
		loc.free(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
		loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
		loc.free(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。
	}
}
